package org.sgmiller.quickstem.tests;

import org.sgmiller.quickstem.Stem;
import org.sgmiller.quickstem.Transaction;

/* The Great Computer Language Shootout
   http://shootout.alioth.debian.org/

   contributed by Jarkko Miettinen
*/

public class binarytreesTransactional {

	private final static int minDepth = 4;

	public static void main(String[] args){
		int n = 0;
		if (args.length > 0) n = Integer.parseInt(args[0]);

		int maxDepth = (minDepth + 2 > n) ? minDepth + 2 : n;
		int stretchDepth = maxDepth + 1;

		Transaction.begin();
		int check = (TreeNode.bottomUpTree(0,stretchDepth)).get().itemCheck();
		System.out.println("stretch tree of depth "+stretchDepth+"\t check: " + check);

		Stem<TreeNode> longLivedTree = TreeNode.bottomUpTree(0,maxDepth);

		for (int depth=minDepth; depth<=maxDepth; depth+=2){
			int iterations = 1 << (maxDepth - depth + minDepth);
			check = 0;

			for (int i=1; i<=iterations; i++){
				check += (TreeNode.bottomUpTree(i,depth)).get().itemCheck();
				check += (TreeNode.bottomUpTree(-i,depth)).get().itemCheck();
			}
			System.out.println((iterations*2) + "\t trees of depth " + depth + "\t check: " + check);
		}
		Transaction.commit();
		System.out.println("long lived tree of depth " + maxDepth + "\t check: "+ longLivedTree.get().itemCheck());
	}


	private static class TreeNode
	{
		private Stem<TreeNode> left, right;
		private Stem<Integer> item;

		TreeNode(int item){
			left=new Stem<TreeNode>(null);
			right=new Stem<TreeNode>(null);
			this.item = new Stem<Integer>(item);
		}

		private static Stem<TreeNode> bottomUpTree(int item, int depth){
			if (depth>0){
				return new Stem<TreeNode>(new TreeNode(
						bottomUpTree(2*item-1, depth-1)
						, bottomUpTree(2*item, depth-1)
						, item
				));
			}
			else {
				return new Stem<TreeNode>(new TreeNode(item));
			}
		}

		TreeNode(Stem<TreeNode> left, Stem<TreeNode> right, int item){
			this.left = left;
			this.right = right;
			this.item = new Stem<Integer>(item);
		}

		private int itemCheck(){
			// if necessary deallocate here
			if (left.get()==null) return item.get();
			else return item.get() + left.get().itemCheck() - right.get().itemCheck();
		}
	}
}
